package com.hardy.leetcode;

import java.util.Stack;

/**
 * Given a string containing just the characters'('and')', find the length of the longest valid
 * (well-formed) parentheses substring. For"(()", the longest valid parentheses substring is"()",
 * which has length = 2. Another example is")()())", where the longest valid parentheses substring
 * is"()()", which has length = 4. User: Ruijie Date: 2016/9/8
 */
public class LongestValidParentheses {

    public static int longestValidParentheses(String s) {
        char[] chs = s.toCharArray();
        Stack<Integer> stack = new Stack<Integer>();
        int last = -1;
        int maxLength = 0;
        for (int i = 0; i < chs.length; i++) {
            if (chs[i] == '(') {
                stack.push(i);
            }
            if (stack.isEmpty()) {
                last = i;
            }
            if(chs[i]==')'){
                if(!stack.isEmpty()){
                    stack.pop();
                    if (!stack.isEmpty()) {
                        maxLength = Math.max(maxLength, i - stack.peek());
                    } else {
                        maxLength = Math.max(maxLength, i - last);
                    }
                }
            }

        }
        return maxLength;
    }

    public static void main(String[] args) {
        String s = "((()";
        System.out.println(longestValidParentheses(s));
    }

}
